package nextGreatestLetter;

//public class Solution {
//    public char nextGreatestLetter(char[] letters, char target) {
//        // 哈希值比target小的最大字符
////        char ans = letters[0];
////        for (int i = 1; i < letters.length; i++) {
////            if(letters[i]>target){
////                ans = letters[i];
////                break;
////            }
////        }
////        return ans;
//
//    }
//}
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int length = letters.length;
        if (target >= letters[length - 1]) {
            return letters[0];
        }
        int low = 0, high = length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (letters[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return letters[low];
    }
}
